from typing import List


class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        row, column = len(grid), len(grid[0])
        if row == 0:
            return sum(grid[0])
        elif column == 0:
            return sum([x[0] for x in grid])

        dp = [[0]*column for _ in range(row)]
        dp[0][0] = grid[0][0]
        for i in range(1, row):
            dp[i][0] = grid[i][0] + dp[i-1][0]
        for j in range(1, column):
            dp[0][j] = grid[0][j] + dp[0][j-1]
        for i in range(1, row):
            for j in range(1, column):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]


if __name__ == '__main__':
    x = Solution()
    print(x.maxValue([[1]]))